package com.github.yangyishe.p200;

/**
 * 125. 验证回文串
 * https://leetcode.cn/problems/valid-palindrome/
 *
 * 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
 *
 * 字母和数字都属于字母数字字符。
 *
 * 给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入: s = "A man, a plan, a canal: Panama"
 * 输出：true
 * 解释："amanaplanacanalpanama" 是回文串。
 * 示例 2：
 *
 * 输入：s = "race a car"
 * 输出：false
 * 解释："raceacar" 不是回文串。
 * 示例 3：
 *
 * 输入：s = " "
 * 输出：true
 * 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
 * 由于空字符串正着反着读都一样，所以是回文串。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 2 * 105
 * s 仅由可打印的 ASCII 字符组成
 *
 */
public class Problem125 {
    public static void main(String[] args) {
        String s="race a car";

        Problem125 problem125 = new Problem125();
        boolean palindrome = problem125.isPalindrome(s);
        System.out.println(palindrome);

    }

    /**
     * 冲撞指针
     * 最关键的, 是将左右指针, 1)判定变化的条件阐明, 2)将变化后可能的副作用阐明(有时可能没有副作用)
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {

        int l=0;
        int r=s.length()-1;
        boolean left2Judge=false;
        boolean right2Judge=false;
        while(l<r){
            // 终结条件: 允许提前因为失败而结束
            // 结束条件: 左右字符均处于待判定状态, 且字符不相等
            // 副作用: 判定后如果相等, 则向内自动推进
            if(left2Judge&&right2Judge){
                if(isCharSame(s.charAt(l),s.charAt(r))){
                    l++;
                    r--;
                    left2Judge=false;
                    right2Judge=false;
                }else{
                    return false;
                }
            }
            // 左索引条件
            // 变化条件: 1. 字符不合法; 或者 2. 字符合法, 且不是待判定状态
            // 副作用: 当字符合法且未处于待判定状态, 则改为待判定.
            // 注: 这里有个隐含前提, 当字符处于待判定的状态时, 必定是合法的.
            if(!left2Judge || !isCharLegal(s.charAt(l))) {
                l++;
                if(!left2Judge&&isCharLegal(s.charAt(l))){
                    left2Judge=true;
                }

            }
            if(!right2Judge||isCharLegal(s.charAt(r))){
                r--;
                if(!right2Judge&&isCharLegal(s.charAt(r))){
                    right2Judge=true;
                }
            }

        }

        return true;
    }

    public boolean isCharLegal(char c){
        return (c>='a'&&c<='z')||(c>='A'&&c<='Z')||(c>='0'&&c<='9');
    }

    public boolean isCharSame(char c1,char c2){
        if(c1>='0'&&c1<='9'){
            return c1==c2;
        }else if(c1>='a'&&c1<='z'){
            return c1==c2||c1-c2=='a'-'A';
        }else{
            return c1==c2||c1-c2=='A'-'a';
        }
    }
}
